#include "../include/base_on_server.h"

using namespace BaseOnServer;
using namespace std::chrono;

u32 const K = 3;
u32 const LIMIT = 100;
u64 sol_cnt = 0;
std::time_t T = std::time(nullptr);
std::time_t max_T;
std::time_t sumTime = 0;
jmp_buf buf;
bool sat(Graph const &g, Set const &s)
{
    u32 n = s.data.size();
    auto f = [&s](u32 x)
    { return s.exist(x); };

    u32 edgeNum = 0;
    for (auto &v : s.data)
    {
        auto &es = g.edges[v];
        edgeNum += std::count_if(es.begin(), es.end(), f);
    }
    edgeNum /= 2;
    int limit = (n * (n - 1) / 2) - K;
    if (limit < 0 || edgeNum >= limit)
        return true;
    return false;
}

void cal(){
    auto avgTime = (float)sumTime/LIMIT;
    std::cout << "find " << LIMIT << " answer cost: " << sumTime << std::endl;
    std::cout << "avg Time cost: " << avgTime <<std::endl;
    exit(0);
}

Set extend(Graph const &g, Set const &s)
{
    Set ret = s;
    u32 n = g.vrt_num;

    for (u32 i = 0; i < n; ++i) {
        if (!ret.exist(i)) {
            ret.add(i);
            if (sat(g, ret)) continue;
            ret.del(i);
        }
    }

    return ret;
}
void print(Set const &c)
{
    ++sol_cnt;
    auto T_now = std::time(nullptr) - T;
    sumTime +=T_now;
    if (T_now > max_T)
    {
        max_T = T_now;
    }
    std::cout << "[" << T_now << "s] No." << sol_cnt << " solution: " << c;
    std::cout << "max_duration: " << max_T <<std::endl;
    T = std::time(nullptr);
}

struct EnumAlmostCoro
{
    enum State
    {
        Start,
        Resume,
        Finish
    };

    State cur;
    Graph const &g;
    Set const &s;
    // almostSat 发起点
    u32 v;
    std::set<Set> save;
    Set value;

    //pick 是待选集合，就是输入的一个极大k-defective图的点集
    Set pick, pos;
//    Vec<Vec<bool>> fakeMatrix;
    EnumAlmostCoro(Graph const &g_, Set const &s_, u32 v_) : cur(Start), g(g_), s(s_), v(v_)
    {
        pos = s;
//        fakeMatrix.resize(g.vrt_num);
//        for (int i = 0; i < fakeMatrix.size(); ++i) {
//            fakeMatrix[i].resize(g.vrt_num);
//        }
    }


    bool operator()()
    {
        u32 i = 1;
        if (cur == Finish)
            return false;
        if (cur == Resume)
            goto CoroResume;
        cur = Resume;

        while (i <= s.data.size())
        {
            while (s.next_pick(i, pos.data, pick.data))
            {
                value = pick + v;
                if (sat(g, value) && save.find(value) == save.end())
                {
                    save.insert(value);
                    return true;
                    CoroResume:;
                }
            }
            i++;
        }
        cur = Finish;
        return false;
    }

//    std::unordered_set<u32> head;
    Set fullConnect;
    // 其中一些关键步骤函数
    // 缺图的右边对应原图的无边
    bool isNeighbor(u32 u,u32 v){
        return g.matrix[u][v]==false?true : false;
    }
//    bool isFakeNerghbor(u32 u,u32 v){
//        return fakeMatrix[u][v]==true?true:false;
//    }
    void updateCanChoose(Set &canChoose,u32 addNode){
        canChoose = canChoose - addNode;
//        // 假如备选集合中的某个点为此次扩充点的邻居且没有访问过，将其加入。
//        for(u32 node :pos.data){
//            if(canChoose.exist(node)){
//                continue;
//            }
//            if((isNeighbor(node,addNode) || isFakeNerghbor(node,addNode)) &&
//               !chosen.exist(node)){
//                canChoose = canChoose + addNode;
//            }
//        }
    }
    int updateK(u32 node,i32 left){
        for(u32 chosenNode:chosen.data){
            if(isNeighbor(node,chosenNode)){
                left--;
            }
        }
        return left;
    }

    // 第一步，预处理.
    // 1.使用伪边，将所有点连到新增点v上。并找出全连接的点集
    // 2.找出所有的全连接点
    void preProcess(){
        // 找到原图中所有的缺陷边
        Set tag;
        for(u32 i=0;i<pos.data.size();i++){
            u32 p = pos.data[i];
            if(isNeighbor(p,v) && !tag.exist(p)){
                tag.add(p);
            }
            for (u32 j = i+1; j < pos.data.size(); j++)
            {
                u32 q = pos.data[j];
                // 如果有边(注意，缺图的有边对应原图的无边)，检查是否有两点都与v相连
                if(isNeighbor(p,q)){
                    if(!tag.exist(p)){
                        tag.add(p);
                    }
                    if(!tag.exist(q)){
                        tag.add(q);
                    }
//                    if(!isNeighbor(p,v)){
//                        fakeMatrix[p][v]=true;
//                        fakeMatrix[v][p]=true;
//                    }
//                    if(!isNeighbor(q,v)){
//                        fakeMatrix[q][v]=true;
//                        fakeMatrix[v][q]=true;
//                    }
                }
            }
        }
        for(u32 node : pos.data){
            if(!tag.exist(node)){
                fullConnect.add(node);
            }
        }
    }
    // void preProcess(){
    //     fakeMatrix.resize(g.vrt_num);
    //     for(int i = 0;i<g.vrt_num;i++){
    //         fakeMatrix[i].resize(g.vrt_num);
    //     }
    //     for (u32 i:pos.data)
    //     {
    //         head.insert(i);
    //     }
    //     for (u32 i = 0; i < pos.data.size(); i++)
    //     {
    //         for(u32 j = i+1;j<pos.data.size();j++){
    //             u32 u = pos.data[i];
    //             u32 v = pos.data[j];
    //             if(isNeighbor(u,v)){
    //                 u>v? head.erase(u):head.erase(v);
    //             }
    //         }
    //     }
    //     int flag=0;
    //     int v;
    //     for(u32 u:head){
    //         if(!flag){
    //             v = u;
    //             continue;
    //         }
    //         fakeMatrix[u][v]=true;
    //         fakeMatrix[v][u]=true;
    //     }
    // }
    // 第二步，开始深度搜索找极大k-defective
    u32 k1;
    Set chosen;

    // 返回值为这个分支中是否有返回过true,如果没有则返回当前值（保证到不了K的缺失图也可以返回）
    bool depthSearch(Set canChoose,i32 left){
        if(left<0){
            return false;
        }
        bool flag = false;
//        sort(canChoose.data.begin(),canChoose.data.end());
//        if(left==0 ){
//            Set res = chosen + fullConnect;
//            if(save.find(chosen) == save.end()){
//                print(res);
//                save.insert(res);
//            }
////          no matter find or not,the result is useful,so return true
//            flag = true;
//        }
        // 记录子分支是否能找到解，找不到将当前的值返回
        // 这里chosen集合的倒退比较容易，就不申请新的空间了
        // canChoose的倒退比较麻烦，申请一份新的存储空间canChoose_c
        for (u32 i = 0; i < canChoose.data.size(); i++)
        {
            Set canChoose_c(canChoose);
            u32 node = canChoose_c.data[i];
            updateCanChoose(canChoose_c,node);
            int left_c = updateK(node,left);
            chosen.add(node);
//            canChoose_c.data.erase(canChoose_c.data.begin()+i);

            if(depthSearch(canChoose_c,left_c)){
                flag = true;
            }
            chosen.del(node);
        }
        if(!flag){
            Set res = chosen + fullConnect;
            if(save.find(chosen) == save.end()){
//                print(res);
                save.insert(res);
            }
        }
//        怪怪的
        return true;
    }

    // 测试版本，使用新设计算法,因使用深度搜索，暂时不知道如何改深度递归
    void enumAlmostSat(){
        i32 left = K;
        preProcess();
        // 深度搜索前的准备工作
        Set canChoose = pos-fullConnect;
        chosen.add(v);
        depthSearch(canChoose,left);
    }
};



void enumAll(Graph &g, Set const &s, std::set<Set> &sol, bool output_flag = true)
{
    for (u32 i = 0; i < g.vrt_num; ++i)
    {
        if (s.exist(i))
            continue;

        auto enumAlmost = EnumAlmostCoro(g, s, i);
        enumAlmost.enumAlmostSat();
//        Set &t = enumAlmost.value;

        for(Set t :enumAlmost.save)
        {
            Set c = extend(g, t);

            if (sol.find(c) == sol.end())
            {
//                if (sol_cnt == LIMIT)
//                {
//                    cal();
//                }
                sol.insert(c);
                if (output_flag)
                    print(c);
                enumAll(g, c, sol, !output_flag);
                if (!output_flag)
                    print(c);
            }
        }
    }
}

//i32 main(){
//    Str input_path = "../data/graph.txt";
//    std::ifstream input_stream(input_path);
//    Graph g;
//    std::set<Set> sol;
//    Set start_set;
//    input_stream >> g;
//    for (u32 i = 0; i < g.vrt_num; ++i) {
//        start_set.add(i);
//    }
//    input_stream.close();
//    EnumAlmostCoro coro(g,start_set,5);
//    coro.enumAlmostSat();
//}
i32 main()
{
    Str input_path = "../data/high_graph.txt";
    std::ifstream input_stream(input_path);
    Graph g;
    std::set<Set> sol;

    input_stream >> g;
    input_stream.close();

    auto tik = system_clock::now();
    // Vec<u32> start_data{0};
    Set start_set;
    start_set = extend(g, start_set);
    sol.insert(start_set);
    print(start_set);

    enumAll(g, start_set, sol);
    auto tok = system_clock::now();

    auto duration = duration_cast<microseconds>(tok - tik);
    std::cout <<  "timeCost:" << double(duration.count()) * microseconds::period::num / microseconds::period::den
              <<  std::endl;

    return 0;
}
